// Created by WXX on 2022/1/21 19:34
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：140 ms, 在所有 C++ 提交中击败了82.21%的用户
 * 内存消耗：68.2 MB, 在所有 C++ 提交中击败了36.54%的用户
 */
class Solution {
public:
    int minJumps(vector<int> &arr) {

        int n = arr.size();
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; i++) pos[arr[i]].push_back(i);

        queue<int> q;
        vector<int> dist(n, -1);
        q.push(0);
        dist[0] = 0;
        while (q.size()) {
            int t = q.front();
            q.pop();

            if (t == n - 1) return dist[t];

            if (pos.count(arr[t])) {
                for (auto v : pos[arr[t]]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[t] + 1;
                        q.push(v);
                    }
                }
                pos.erase(arr[t]);  // 必须加上这一句，否则超时
            }

            if (t - 1 >= 0 && dist[t - 1] == -1) {
                dist[t - 1] = dist[t] + 1;
                q.push(t - 1);
            }
            if (t + 1 < n && dist[t + 1] == -1) {
                dist[t + 1] = dist[t] + 1;
                q.push(t + 1);
            }
        }
        return -1;
    }
};

int main() {

    vector<int> arr = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404};
    cout << Solution().minJumps(arr) << endl;

    return 0;
}
